
import java.io.* ;
public class Main{
	private static Avl[] hashT=null;
	private static int N;
	private static String output;   //the output 
	
	/**
	 * The first hash function, used to map Id numbers to a hash table pointing to AVL trees
	 * @param id - The integer to calc the Hash for.
	 * @return the hash function result
	 */
	private static int HashFuncA(int id)
	{
		return id%(hashT.length);
	}
	
	/**
	 * The second hash function, used to position Id numbers inside the plane array
	 * @param id - The integer to calc the Hash for.
	 * @return the hash function result
	 */
	private static int HashFuncB(int id)
	{
		return id%(N);
	}
	
	/**
	 * The the third hash function, used to position Id numbers inside the plane array
	 * @param id - The integer to calc the Hash for.
	 * @return the hash function result
	 */
	private static int HashFuncC(int id)
	{
		int r=revInt(id);
		return (r%(N));
	}
	
 public static void main(String[] args){
   	
	 	// OUTPUT FILE //
	 	output=args[2];
	 	//////////////////// REGISTRY
 	    String str = read_From_File(args[0]);//read the file to a string
 	    String[] ids = str.split(",");//now you have an array of ids as strings (but they contain spaces)
 	    N = ids.length;//this is N - the amount of ids

 	    for(int i = 0; i <N ;i++)
	    {
	    	ids[i] = ids[i].trim();//remove spaces
	    }
 	    
 	    int[] regIDS=convertStringArrToInt(ids);
 	    ids=null;
 	    
 	    Register(regIDS);
 	    
 	    ///////////////////// CHECKIN
 	    str = read_From_File(args[1]);//read the file to a string
	    ids = str.split(",");//now you have an array of ids as strings (but they contain spaces)
	   
	    for(int i = 0; i <ids.length ;i++)
	    {
	    	ids[i] = ids[i].trim();//remove spaces
	    }
	    
	    int[] checkinIDS=convertStringArrToInt(ids);
	    ids=null;
 	    List regList = CheckIn(checkinIDS);
 	    
 	    /////// Boarding /////////////
 	    int[][] stats=boarding(regList);
 	   
	    write_To_File(output,calcBoardingStats(stats, 0));
	    write_To_File(output, "\n");
 	    write_To_File(output,calcBoardingStats(stats, 1)); 	   
   }
 
/**
 *    
 * @param stats - an array of the stats from the 2 hashfunctions
 * @param func_num - the number of the hash function we intrested to get results about 
 * @return a string containing the details about the specific hash function, from the 4 requested sums  
 */
   private static String calcBoardingStats(int[][] stats,int func_num)
   {
	   int[] sum1= new int[4];
	    for(int i=0;i<stats[0].length/2;i++)
	    {
	    	sum1[0]=sum1[0]+stats[func_num][i];
	    }
	    
	    for(int i=0;i<(stats[0].length*3/4);i++)
	    {
	    	sum1[1]=sum1[1]+stats[func_num][i];
	    }
	    
	    for(int i=0;i<stats[0].length-(int)Math.sqrt(stats[0].length);i++)
	    {
	    	sum1[2]=sum1[2]+stats[func_num][i];
	    }
	    
	   for(int i=stats[0].length-(int)Math.sqrt(stats[0].length);i<stats[0].length;i++)
	    {
		   sum1[3]=sum1[3]+stats[func_num][i];
	    }
	   
	    return (sum1[0]+", "+sum1[1]+", "+sum1[2]+", "+sum1[3]);	   
   }
   
   
   public static String read_From_File(String inputFilename){
	    String idsString = "" ;
        try {
            File inFile = new File(inputFilename);
            FileReader ifr = new FileReader(inFile);
            BufferedReader ibr= new BufferedReader(ifr) ;

            String tempLine = "" ;
           
            while (tempLine != null )
            {
            	tempLine = ibr.readLine() ;
                if (tempLine != null)
                {
                	idsString += tempLine;
                }
            }
            
            ibr.close();
            ifr.close();
            
        }

        catch(Exception e) {
            System.out.println( "Error \""+ e.toString()+ "\" on file "+inputFilename);
            e.printStackTrace() ;
            System.exit(-1) ;      //brutally exit the program
        }
        return idsString;

    }


    private static void write_To_File(String outputFilename,String str) {

        
        try {
            File outFile = new File(outputFilename);
            FileWriter ofw = new FileWriter(outFile, true);

            
          	ofw.append(str+"");

            ofw.close();
        }
        catch (Exception e) {
            System.out.println( "Error \""+ e.toString()+ "\" on file "+outputFilename);
            e.printStackTrace() ;
            System.exit(-1) ;      //brutally exit the program
        }

    }
    
    /**
     * get an array of strings, when each string represent a number.
     * convert each string into the number it represent. 
     * @param ids - array of strings, when each string represent a number.
     * @return array of the numbers the strings at param represented
     */
    private static int[] convertStringArrToInt(String[] ids)
	{
		int[] registryIDs=new int[ids.length]; 
			for(int i=0;i<ids.length;i++)
			{
				int IDint=0;
				String IDstring=ids[i];
				for(int j=0;j<IDstring.length();j++)
				{
					int digit=IDstring.charAt(j)-'0';
					IDint=IDint+(digit*(int)(Math.pow(10,IDstring.length()-1-j)));
				}
				registryIDs[i]=IDint;
			}
		
		return registryIDs;
	}
  /**
   * An integer reversal function  
   * @param id - The integer to be reversed
   * @return The integer in reverse digit order. <br> <b>example:</b> revInt(1234) returns 4321.
   */
  private static int revInt(int id)
  {
	  int ans=0;
	  while(id>0)
	  {
		  ans=ans*10+id%10; 
		  id=id/10;
	  }
	  return ans;
  }
  /**
   * This function hadles the sitting arrangement for the plane using two hashing algorithms and linear probing
   * 
   * @param regList - The FIFO list of people who are boarding the plane
   * @return A 2XN array containing the number of steps necesery for a passanger to find a seat.<br> The first array is the stats for the first hash function and the second is for the second one. 
   */
  private static int[][] boarding(List regList)
  {
	  int[][] plane = new int[2][hashT.length*3];
	  int[][] stats = new int[2][hashT.length*3];
	  int boarded=0;
	  while(boarded<plane[0].length && !regList.isEmpty())
	  {
		  int step,counter;
		  int id=regList.dequeue();
		  int i=HashFuncB(id);
		  int j=HashFuncC(id);
		  step=0;
		  counter=1;
		  while(plane[0][i+step]!=0)
		  { 
			  counter++;
			  
			  if(step>0)
			  {
				  if(i-step>=0)
					  step=step*-1;
				  else
					  step++;
			  }
			  else
				  {
				  if(i-step+1<plane[0].length)
					  step=(step*-1)+1;
				  else
					  step--;
				  }
		  }
		  plane[0][i+step]=id;
		  stats[0][boarded]=counter;
		  step=0;
		  counter=1;
		  while(plane[1][j+step]!=0)
		  { 
			  
			  counter++;
			  if(step>0)
			  {
				  if(j-step>=0)
					  step=step*-1;
				  else
					  step++;
			  }
			  else
				  {
				  if(j-step+1<plane[0].length)
					  step=(step*-1)+1;
				  else
					  step--;
				  }
		  }
		  plane[1][j+step]=id;
		  stats[1][boarded]=counter;
		  boarded++;
	  }
	  return stats;
  }
 
  /**
   * 
   * enter the people who register to the flight into an hash table of AVL trees (hashT).
   * and print the table's Avl trees size and height 
   * @param id - an array of Ids of people register to the flight    
   */
  private static void Register(int[] id)
  {
	  hashT=new Avl[id.length/3];
		for(int i=0;i<id.length;i++)
		{
			int HashF=HashFuncA(id[i]);
			if(hashT[HashF]==null)
				hashT[HashF]=new Avl();
			hashT[HashF].Insert(id[i],null);		
		}
		
		for(int i=0;i<hashT.length;i++)
		{
			if(hashT[i]!=null)
				write_To_File(output,hashT[i].getAVLHeight()+","+hashT[i].getSize()+" ");
			else
				write_To_File(output,0+","+0+" ");
		}
		write_To_File(output, "\n");
  }
  
  /**
   * do the checkin process - get a list of arriving people to flight and 
   * check-in first the registered people to flight and later the unregisted.
   * -print the number of average steps it took to find whether each person is registed to flight.
   * -print the list of people getting on board sorted by id number from small to big.  
   * @param ids - an array of people's ids arraving to the airport, sorted by time of arrival
   * @return a List of the checkin list - 
   * 		 the arraving people ids(ids array) sorted by priority to get on board the plane -
   * 		 registered first and unregisted later, while arrival time stay also stable
   */
  private static List CheckIn(int[] ids)
  {
	  List regList=new List();
	  List unregPassangers=new List();
	  int CheckCounterSum=0;
	  //int free=N;
	  //free>0 &&
	  int i=0;
	  while(i<ids.length)		//while there is free space on plane
	  {
		  int isReg=SearchID(ids[i]);
		  if(isReg>0)	//ID registered
		  {
			  regList.enqueue(ids[i]);
			//  free--; 		//the plane has one less space 
		  }
		  else		//ID is UNregistered
		  {
			  unregPassangers.enqueue(ids[i]);
		  }
		  CheckCounterSum=CheckCounterSum+Math.abs(isReg);
		  i++;
	  }

//////print average of checks	//////////

	  write_To_File(output,""+(CheckCounterSum/i));
	  write_To_File(output, "\n");
	  
	  //chain both lists to one list
	  List tempSortList=new List(regList,unregPassangers); //list for sorting and printing
	  List CheckinList=new List(regList,unregPassangers);	//list for return

		/////// create sorted-by-number passangers list array //////////  
	  int[] sortedPasList=InsertionSort(tempSortList);
	  //////////// print sortedPasList //////////////

	  for(int j=0;j<sortedPasList.length;j++)
	  {
		  if(j!=0)
			  write_To_File(output,", ");
		  write_To_File(output,""+sortedPasList[j]);
	  }
	  	write_To_File(output, " \n");
	  
	  return CheckinList;
  }
 
  /**
   * search a specific Id inside the hash table HashT
   * @param id - the specific Id number we want to find if exist
   * @return an integer defining how many steps it took to determine whether the id exist in HashT:
   * 			>0 - the id exist in HashT
   * 			<0 - the id doesn't exist in HashT
   * 			|integer| = the number of steps it took
   */
   private static int SearchID(int id)
	{
		int index=HashFuncA(id);
		if(hashT[index]==null)
			return -1;
		else
			return hashT[index].Search(id);
	}
   
   /**
    * sort a list of numbers from smallest to largest, by insertion sort 
    * @param list - a list containing id numbers
    * @return a new sorted list from smallest id to largest
    */
   private static int[] InsertionSort(List list)
   {
	   int[] ans=new int[N];
	   int j,temp;
	   for(int i=0;i<N && !list.isEmpty();i++)
	   {
		   j=i;
		   ans[j]=list.dequeue();
		   while(j>0 && ans[j-1]>ans[j])
		   {
			   temp=ans[j-1];
			   ans[j-1]=ans[j];
			   ans[j]=temp;
			   j--;
		   }
	   }
	   return ans;	  			  
   }
}
    
  